As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. To ensure data integrity, an error correcting Reed-Solomon (RS) code is often used. Many communications systems perform forward error correction (FEC) to improve data transmission accuracy and to ensure data integrity. FEC helps reduce bit error rates (BER) in applications such as data storage, digital video broadcasts, and wireless communications. Reed-Solomon (RS) error-correcting codes are commonly used for FEC.
Referring now to FIG. 1, a first device 10-1 communicates with a second device 10-2 over a communications channel 12. The communications channel can be hardwired or wireless. For example, the communications channel 12 can be an Ethernet network, a wireless local area network, a bus for a hard drive, etc. The first device 10-1 includes components 14-1 that output signals to a RS encoder 16-1 and that receive signals from a RS decoder 18-1. Likewise, the device 10-2 includes components 14-2 that output signals to a RS encoder 16-2 and that receive signals from a RS decoder 18-2. The components 14-1 of the first device 10-1 may be similar to or different than the components 14-2 of the second device 10-2. The encoders 16 encode the data before the data is output onto the communications channel 12. The encoders 16 insert redundant bits into the data stream. The decoders 18 use the redundant bits to detect and, when possible, to correct errors in the received data.
Referring now to FIG. 2A, steps that are performed by a RS decoder are shown generally at 20. In step 22, the RS decoder computes syndrome values. In step 24, the RS decoder computes an error locator polynomial. The error locator polynomial can be calculated using a Berlekamp-Massey algorithm (BMA), inversionless BMA (iBMA), Euclidean algorithm, or other suitable algorithms. In step 26, the Reed-Solomon decoder calculates an error evaluator polynomial, which is typically based on the syndrome values and the error locator polynomial.
In step 28, the RS decoder finds error locations. For example, Chien's search algorithm, which will be described below, can be used. In step 30, error values are found. For example, Forney's algorithm, which will be described below, is often used to find the error values. Steps 28 and 30 may be performed in parallel in hardware implementations.
Referring now to FIG. 2B, a RS decoder 32 typically includes a syndrome calculator 34 and an error locator polynomial generator 36, which employs Euclidean, Berlekamp-Massey or other algorithms. The RS decoder 32 also includes an error evaluator polynomial generator 38, an error location finder 40 and a error value finder 42. Control devices 44 and storage devices 46 may also be used to control decoding and to store data values for use by the RS decoder 32. The RS decoder 32 can be implemented using register-based VLSI, software and a processor, an application specific integrated circuit (ASIC) or in any other suitable manner.
The error location search can be performed using Chien's search, which is disclosed in R. T. Chien, “Cyclic Decoding Procedure for the Bose-Chandhuri-Hocquenghem Codes”, I.E.E.E. Transactions on Information Theory, Vol. IT-10, pp. 357–363, October 1964, which is hereby incorporated by reference in its entirety. The error value computation can be performed using Forney's algorithm disclosed in G. D. Forney, “On Decoding BCH Codes”, I.E.E.E Transactions on Information Theory, Vol. IT-11, pp. 549–557, October 1965, which is hereby incorporated by reference in its entirety.
While a data storage system will be used below to illustrate the operation of a Reed-Solomon decoder, skilled artisans will appreciate that there are may other uses for Reed-Solomon decoders. In the data storage system illustrated in FIG. 3, the Reed-Solomon decoder 32 receives sequential sectors or codewords 50-1, 50-2, 50-3 . . . , and 50-n. While the first codeword 50-1 is received, the Reed-Solomon decoder 32 computes the syndrome values for the first codeword 50-1 as shown at 52. While the second codeword 50-2 is received, the Reed-Solomon decoder 32 computes the error locator polynomial and then performs error location search and error value computations for the first codeword 50-1 as shown at 54. While the second codeword 50-2 is received, the Reed-Solomon decoder 32 also computes the syndrome values for the second codeword 50-2 as shown at 55. Operation continues in this manner for subsequent codewords.
The syndrome computation for an nth codeword must be completed by the end of the nth codeword. The error location search and error value computations for the nth codeword must be completed by the end of the (n+1)th codeword. The syndrome computation operates under the symbol clock fsymbol. The error location search and error value computations operate under a system clock fsystem.
The Reed-Solomon decoder 32 operates based on finite fields GF(2m) where each symbol is an m-bit binary symbol εGF(2m). A Reed-Solomon code with correcting power t has a generator polynomial G(x) over GF(2m) with 2t roots:G(x)=(x+αb) . . . (x+αb+2t−2)(x+αb+2t−1)G(x)=x2t+g2t-1x2t−1+ . . . +g1x1+g0x0.where giεGF(2m). A Reed-Solomon code word can be represented using polynomial C(x):C(x)=cn-1xn−1+ . . . +c1x1+c0x0 C(x)=x2t(dk-1xk+1+ . . . +d0x0)+(r2t-1x2t−1+ . . . +r0x0)C(x)=x2tD(x)+R(x).where D(x) represents the data symbols to be encoded and R(x) represents the Reed-Solomon parity symbols. The received code word can be represented using polynomial V(x):V(x)=vn-1xn−1+ . . . +v1x1+v0x0 V(X)=(cn-1xn−1+ . . . +c0x0)+(en-1xn−1+ . . . +e0x0)V(x)=C(x)+E(x).where C(x) is the polynomial representing the Reed-Solomon codeword and E(x) is a polynomial representing the error vector.
During the decoding of a Reed-Solomon code, a set of 2t syndromes S0, S1, . . . , S2t-1 is first computed as shown in step 22 of FIG. 2A by evaluating V(x) at αi:
      S    j    =                    ∑                  i          =          0                          n          -          1                    ⁢                          ⁢              V        ⁡                  (                      α                          i              ⁡                              (                                  b                  +                  j                                )                                              )                      =                  ∑                  i          =          0                          n          -          1                    ⁢                        v          i                ⁢                              α                          i              ⁡                              (                                  b                  +                  j                                )                                              .                    Next, in step 24 of FIG. 2A, an error locator polynomial ^(x) of degree t is computed from the syndromes S0, S1, . . . , S2t-1. For example, an inversion-less Berlekamp-Massey algorithm (iBMA) is typically employed, although other algorithms can be used. Further details concerning the iBMA approach can be found in “Inversionless Decoding of Both Errors and Erasures of Reed-Solomon Code”, I.E.E.E. Transactions on Communications, Vol. 46, No. 8, August 1998), which is hereby incorporated by reference in its entirety. A scratch polynomial B(x) of degree 2t is also used in the iBMA computation.
Referring now to FIG. 4, steps of the iBMA algorithm are shown. In step 56, initialization of the error locator polynomial (^(x)=1), the scratch polynomial (B(x)=1), indexes (r=0, L=0) and previous discrepancy (ΔB=1) is performed. If r=2t, as determined in step 57, control ends in step 58. Otherwise the discrepancy Δ is computed in step 60:Δ=Σt=0LΛtSr-1 Next, ^(x), B(x), L and ΔB are updated according to rules in box 62. If Δ# 0 as determined in step 64, ^(x) is set equal to ΔB^(x)+ΔxB(x) in step 66. Otherwise, (x) is set equal to ^(x) in step 68. If Δ≠0 and 2L≦r as determined in step 72, B(x) is set equal to ^(x), L is set equal to r+1−L, and ΔB is set equal to Δ in step 74. Otherwise, B(x) is set equal to xB(x) in step 76. In step 80, r is incremented. Control loops from step 80 to step 57.
To find the error locations, a search algorithm such as Chien's search is used to evaluate ^(x) at 1, α−1, α−2, . . . , α−(n−1), where ^(α−i)=0 implies vi is a symbol with error. For error value computation, Forney's algorithm is typically used to compute error values at α−i, where ^(a−i)=0. An error evaluator polynomial is defined by Ω(x)=^(x)S(x)modx2t, where S(x) is the syndrome polynomial. Then, the error value at location α−1 is given by:
            x      b        ⁢          Ω      ⁡              (        x        )                  x    ⁢                  ⁢                  Λ        ′            ⁡              (        x        )            wherein Λ′(x) is a formal derivative of Λ(x).
A parallel architecture can be used for the iBMA algorithm implementation. Referring now to FIG. 5A, an iBMA circuit 100 for implementing the iBMA with t=3 is shown. As can be appreciated, t can have higher or lower values. The iBMA circuit 100 includes delay devices 102 (such as registers), finite field adders 104, and finite field multipliers 106.
The discrepancy value Δ is computed by multiplying syndromes S0, S1, . . . , S5 with the error locator polynomial coefficients ^0, ^1, ^2, and ^3, respectively, using multipliers Sm0, Sm1, Sm2, and Sm3, respectively. Outputs of multipliers Sm0 and Sm2 are summed by adder 110 to provide an even portion of Δeven discrepancy Δ. Outputs of multipliers Sm1 and Sm3 are summed by adder 112 to provide an odd portion of Δodd discrepancy Δ. (Such a separation of Δeven and Δodd is because of the hardware reuse of iBMA and error evaluation circuit. Δodd is used in the evaluation of xΛ′(x) in the Feng or Forney method.) Δeven and Δodd are summed by adder 114 to provide discrepancy Δ, which is fed back to multipliers Bm0, Bm1, Bm2, and Bm3.
Discrepancy Δ is also fed back through delay device 116 to conditionally update the value of the previous discrepancy ΔB. ΔB is fed to the inputs of multipliers ^m0, ^m1, ^m2, and ^m3. Multipliers Bm0, . . . , Bm3 and ^m0, . . . , ^m3 are used in the computation of the updated value of ^(x) according to FIG. 4, step 66. A condition circuit 116 tracks index variables L, r and the discrepancy value Δ to determine the updated ^(x) and B(x) values according to FIG. 4 steps 64 and 72.
FIG. 5B shows the computation schedule of the iBMA of the iBMA algorithm using the circuit in FIG. 5A, where each iBMA iteration is finished within one clock cycle. In a first half of the clock cycle of a first iteration, syndrome values are calculated. In a second half of the clock cycle of the first iteration, the syndrome values are used to generate error locations and to compute error values. The critical path is the feedback loop within the iBMA iterations. In each iBMA iteration, the critical path involves the computation of the discrepancy value Δ followed by the computation of ^(x) and B(x). As the clock speed increases, it has become more difficult to complete one iBMA iteration within one clock cycle.